SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Interlock protocol</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Interlock protocol</span></span>

</h1>

</header>

<p>In <a href="Cryptography" title="Cryptography">cryptography</a>, the <b>extension lock protocol</b>, as described by <a href="Ron_Rivest" title="Ron Rivest">Ron Rivest</a> and <a href="Adi_Shamir" title="Adi Shamir">Adi Shamir</a>, is a <a href="Cryptographic_protocol" title="Cryptographic protocol">protocol</a> designed to frustrate eavesdropper attack against two parties that use an anonymous <a href="Key_exchange" title="Key exchange">key exchange</a> protocol to secure their conversation. A further paper proposed using it as an <a href="Authentication_protocol" title="Authentication protocol">authentication protocol</a>, which was subsequently broken.

</p>

<div class="mw-heading mw-heading2"><h2 id="Brief_history">Brief history</h2></div>

<p>Most cryptographic protocols rely on the prior establishment of secret or public keys or passwords. However, the <a href="Diffie%E2%80%93Hellman_key_exchange" title="Diffie–Hellman key exchange">Diffie–Hellman key exchange</a> protocol introduced the concept of two parties establishing a secure channel (that is, with at least some desirable security properties) without any such prior agreement. Unauthenticated Diffie–Hellman, as an anonymous key agreement protocol, has long been known to be subject to <a href="Man_in_the_middle_attack" class="mw-redirect" title="Man in the middle attack">man in the middle attack</a>. However, the dream of a "zipless" mutually authenticated secure channel remained.

</p><p>The Interlock Protocol was described<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> as a method to expose a middle-man who might try to compromise two parties that use anonymous key agreement to secure their conversation.

</p>

<div class="mw-heading mw-heading2"><h2 id="How_it_works">How it works</h2></div>

<p>The Interlock protocol works roughly as follows:

</p>

<ol><li>Alice encrypts her message with Bob's key, then sends half her encrypted message to Bob.</li>

<li>Bob encrypts his message with Alice's key and sends half of his encrypted message to Alice.</li>

<li>Alice then sends the other half of her message to Bob, who sends the other half of his.</li></ol>

<p>The strength of the protocol lies in the fact that half of an encrypted message cannot be decrypted. Thus, if Mallory begins her attack and intercepts Bob and Alice's keys, Mallory will be unable to decrypt Alice's half-message (encrypted using her key) and re-encrypt it using Bob's key. She must wait until both halves of the message have been received to read it, and can only succeed in duping one of the parties if she composes a completely new message.

</p>

<div class="mw-heading mw-heading2"><h2 id="The_Bellovin/Merritt_Attack">The Bellovin/Merritt Attack</h2></div>

<p>Davies and Price proposed the use of the Interlock Protocol for authentication in a book titled <u>Security for Computer Networks.</u><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> But an attack on this was described by <a href="Steven_M._Bellovin" title="Steven M. Bellovin">Steven M. Bellovin</a> & Michael Merritt.<sup id="cite_ref-bellovin_3-0" class="reference"><a href="#cite_note-bellovin-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> A subsequent refinement was proposed by Ellison.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p><p>The Bellovin/Merritt attack entails composing a fake message to send to the first party. Passwords may be sent using the Interlock Protocol between A and B as follows:

</p>

<pre> A B

Ea,b(Pa)<1>------->

<-------Ea,b(Pb)<1>

Ea,b(Pa)<2>------->

<-------Ea,b(Pb)<2>

</pre>

<p>where Ea,b(M) is message M encrypted with the key derived from the Diffie–Hellman exchange between A and B, <1>/<2> denote first and second halves, and Pa/Pb are the passwords of A and B.

</p><p>An attacker, Z, could send half of a bogus message—P?--to elicit Pa from A:

</p>

<pre>A Z B

Ea,z(Pa)<1>------>

<------Ea,z(P?)<1>

Ea,z(Pa)<2>------>

Ez,b(Pa)<1>------>

<------Ez,b(Pb)<1>

Ez,b(Pa)<2>------>

<------Ez,b(Pb)<2>

</pre>

<p>At this point, Z has compromised both Pa and Pb. The attack can be defeated by verifying the passwords in parts, so that when Ea,z(P?)<1> is sent, it is known to be invalid and Ea,z(Pa)<2> is never sent (suggested by Davies). However, this does not work when the passwords are hashed, since half of a hash is useless, according to Bellovin.<sup id="cite_ref-bellovin_3-1" class="reference"><a href="#cite_note-bellovin-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> There are also several other methods proposed in,<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> including using a <a href="Shared_secret" title="Shared secret">shared secret</a> in addition to the password. The forced-latency enhancement can also prevent certain attacks.

</p>

<div class="mw-heading mw-heading2"><h2 id="Forced-Latency_Interlock_Protocol">Forced-Latency Interlock Protocol</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>A modified Interlock Protocol can require B (the server) to delay all responses for a known duration:

</p>

<pre>A B

Ka------------->

<-------------Kb

Ea,b(Ma)<1>---->

<----Ea,b(Mb)<1> (B delays response a fixed time, T)

Ea,b(Ma)<2>---->

<----Ea,b(Mb)<2> (delay again)

<----------data

</pre>

<p>Where "data" is the encrypted data that immediately follows the Interlock Protocol exchange (it could be anything), encoded using an <a href="All-or-nothing_transform" title="All-or-nothing transform">all-or-nothing transform</a> to prevent in-transit modification of the message. Ma<1> could contain an encrypted request and a copy of Ka. Ma<2> could contain the decryption key for Ma<1>. Mb<1> could contain an encrypted copy of Kb, and Mb<2> could contain the decryption key for Mb<1> and the response, such as OK, or NOT FOUND, and the hash digest of the data.

</p><p>MITM can be attempted using the attack described in the Bellovin paper (Z being the man-in-the-middle):

</p>

<pre>A Z B

Ka------------->Kz------------->

<---------------Kz<-----------Kb

Ea,z(Ma)<1>---->

<----Ea,z(Mz)<1> (delayed response)

Ea,z(Ma)<2>---->

Ez,b(Ma)<1>----->

<-----Ez,b(Mb)<1> (delayed response)

<----Ea,z(Mz)<2>

Ez,b(Ma)<2>----->

<-----Ez,b(Mb)<2> (delayed response)

<------------data

<----------data

</pre>

<p>In this case, A receives the data approximately after 3*T, since Z has to perform the interlocking exchange with B. Hence, the attempted MITM attack can be detected and the session aborted.

</p><p>Of course, Z could choose to not perform the Interlock Protocol with B (opting to instead send his own Mb) but then the session would be between A and Z, not A, Z, and B: Z wouldn't be in the middle. For this reason, the interlock protocol cannot be effectively used to provide authentication, although it can ensure that no third party can modify the messages in transit without detection.

</p>

<ul><li><a href="Computer_security" title="Computer security">Computer security</a></li>

<li><a href="Cryptanalysis" title="Cryptanalysis">Cryptanalysis</a></li>

<li><a href="Secure_channel" title="Secure channel">Secure channel</a></li>

<li><a href="Key_management" title="Key management">Key management</a></li>

<li><a href="Cryptographic_protocol" title="Cryptographic protocol">Cryptographic protocol</a></li>

<li><a href="Opportunistic_encryption" title="Opportunistic encryption">Opportunistic encryption</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">R. Rivest and A. Shamir. How to Expose an Eavesdropper. CACM, Vol. 27, April 1984, pp. 393-395. <a rel="nofollow" class="external autonumber" href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.159.1673&rep=rep1&type=pdf">[1]</a></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text">D. W. Davies and W. L. Price. Security for Computer Networks. John Wiley & Sons, second ed., 1989.</span>

</li>

<li id="cite_note-bellovin-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-bellovin_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-bellovin_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text">S. M. Bellovin and M. Merritt. <a rel="nofollow" class="external text" href="https://www.cs.columbia.edu/~smb/papers/interlock.pdf">An Attack on the Interlock Protocol When Used for Authentication</a> (PDF). I.E.E.E. Transactions on Information Theory, v. 40, n. 1, January 1994, pp. 273-275.</span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text">C. Ellison. Establishing Identity Without Certification Authorities. Proceedings of the Sixth Annual USENIX Security Symposium, San Jose, July 1996, pp. 67-76.</span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text">R. H. Morris and K. Thompson, "Unix password security," <i>Communications of the ACM</i>, vol. 22, p. 594, November 1979</span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text">F. T. Grampp and R. H Morris, "Unix operating system security," <i>AT&T Bell Laboratories Technical Journal</i>, vol. 63 pp. 1649-1672, October 1984</span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text">D. V. Klein, "Foiling the cracker": A survey of, and improvements to, password security," in <i>Proceedings of the USENIX UNIX Security Workshop</i>, (Portland), pp. 5-14, August 1990</span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text">P. Leong and C. Tham, "Unix password encryption considered insecure" in <i>Proc. Winter USENIX Conference</i>, (Dallas), 1000</span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.quadibloc.com/crypto/mi060709.htm">Interlock protocol for authentication</a></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20040509082559/http://lists.virus.org/cryptography-0310/msg00083.html">Full-Duplex-Cube Grandmaster (was: anonymous DH & MITM)</a></li>

<li><a rel="nofollow" class="external text" href="http://zooko.com/fit_against_middleperson_fillinthecoins.html">Defense Against Middleperson Attacks (Zooko's Forced-Latency Protocol)</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-29" href="https://en.wikipedia.org/wiki/?title=Interlock_protocol&oldid=1303257570">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>